Reading assessment 2 and Programming assignment 2 due today at 8pm on Gradescope.
Quiz 1 during the Monday, February 5 discussion sections.
Reading assessment 3 released today, due in 1 week on Thursday 2/8
A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending.
– Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System
By the end of today's lecture, you will learn:
⚠ Warning: The cryptocurrency market is incredibly volatile. Investing in cryptocurrencies is a bad way to make money, and a good way to lose money. Do not invest in cryptocurrencies!
With that warning stated: we're going to explore the world of cryptocurrencies in Part 2 of this class, for two reasons.
Our starting point into cryptocurrencies is to build a digital version of a banking system, where people can transfer money to each other electronically over the Internet without the need for a single trusted banking authority.
Our digital money system should be "secure" against "powerful adversaries."
(We will make more precise today both the security requirements and the kinds of adversaries that we can withstand.)
| Alice | Mallory | Bob | ||
|---|---|---|---|---|
| $\longrightarrow$ | $\longrightarrow$ |
In the physical world, when Bob receives a check from Alice, he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.
Alice properly signed the check
Alice possesses $1 in her bank account
Alice does not double spend the money by writing a check to someone else at the same time
For a digital monetary system:
A ledger is a book or collection of accounts in which account transactions are recorded. Each account has an opening or carry-forward balance, and would record each transaction as either a debit or credit in separate columns, and the ending or closing balance.
For every debit recorded in a ledger, there must be a corresponding credit, so that the debits equal the credits in the grand totals.
Source: Wikipedia
Source: Wikipedia
Imagine for the moment that there was a book that is:
If you had such a ledger, then you can emulate the bank!
Bitcoin is a public and peer-to-peer cryptocurrency. It is a digital coin, combined with a digital ledger that keeps track of how many Bitcoins each party holds at any moment in time.
Rather than relying on a bank, the Bitcoin ledger is maintained by everyone running the Bitcoin software. Anyone can run the Bitcoin software and store a copy of the ledger on their computer.
Bitcoin was invented in 2009 by an anonymous party (or parties) holding the pseudonym Satoshi Nakamato.
While we will focus today on financial transactions, in principle you can store any data on Bitcoin.
The first transaction on the Bitcoin blockchain encodes the following message: "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks". This message was in reference to an article posted in a British newspaper on January 3, 2009.
[Image source: https://en.bitcoin.it/]
Because the Bitcoin ledger is public, anyone can read any message that has ever been stored on the blockchain.
# This code connects to a bitcoin node (hosted on https://mempool.space)
# holding the full bitcoin blockchain and extracts the first message
# encoded in the genesis block of the coinbase transaction.
import requests
from binascii import unhexlify
# getting the block id for the genesis block (block 0).
genesis_block_id = requests.get('https://mempool.space/api/block-height/0').text
# getting all the block transactions of block 0 and parsing it
response = requests.get('https://mempool.space/api/block/' + genesis_block_id + '/txs')
# decode the special message in the genesis block
print(unhexlify(response.json()[0]['vin'][0]['scriptsig_asm'].split(" ")[5]).decode('ascii'))
The Times 03/Jan/2009 Chancellor on brink of second bailout for banks
Returning back to the topic of financial transactions: if you have a public ledger that is also append-only, then you could use it to:
In fact, you don't even need to do both! One can be inferred from the other.
The account model is what we are used to from the traditional banking system. In this approach, the bank maintains a list of every account and its current balance. When a transaction is submitted, the bank updates its record of accounts by debiting the sender and crediting the receiver.
Most cryptocurrencies work in the other direction: they store a public ledger containing every financial transaction ever made. This is called the unspent transaction output model, or UTXO.
In the UTXO model, for a transaction to be valid:
[Image source: researchgate.net]
Or to think about it another way: the ledger records the movement of each individual coin in the system. Each coin is handed to the next person when its current owner produces a digital signature that publicly attests to the fact that the coin is being given to someone new.
Transactions in Bitcoin act slightly different than checks do in the physical world.
[Image source: Nakamoto whitepaper]
The data structure for Bitcoin's public ledger is called a blockchain. It is a sequence of blocks, which themselves contain several transactions.
If everyone acts honestly, the intention is that new blocks are only added to the end of the chain.
In more detail: a Bitcoin transaction is a single money transfer, just like a written check from a sender to a receiver. But unlike a check:
Transactions are irrevocable. If you make a mistake and send your money to the wrong place, it is gone forever!
(Note: transactions in Bitcoin are actually more complicated than just a digital signature; they can involve more sophisticated computer scripts. We will return to this point in a future lecture.)
The transactions are then grouped into blocks.
The blocks are linked together into a blockchain.
Every block references the hash of the previous block.
[Image source: Nakamoto whitepaper]
Example. Here is a screenshot of some blocks that were mined, or created, yesterday afternoon. There is also one partial block that is in the process of being formed.
[Source: mempool.space, at block 828285]
I took these screenshot using a blockchain explorer at the website mempool.space. But you don't have to trust this website; anyone can run a the Bitcoin software and join the peer-to-peer network to see these blocks and transactions as they appear.
As the screenshot shows, there are over 800,000 blocks in the Bitcoin network at the moment. Collectively, they hold almost 1 billion transactions.
The signatures in these transactions add up quickly in size! At the moment, the blockchain is around 545 GB in size. So anyone can download the ledger, but it might take you awhile to do so.
The most important property of the Bitcoin blockchain is that all participants eventually reach agreement over the state of the ledger. If I believe that Alice owns 3 coins, then (eventually) so should you.
Agreement should be possible even if some of the participants are trying to tamper with or censor the ledger.
More specifically, we want a blockchain to achieve two types of agreement properties.
(Note the use of the word "eventually" in each claim. We'll come back to that in a bit, and discuss how long "eventually" might take.)
At a high level, there are three types of participants within Bitcoin.
A light client only needs to hold one or more secret keys for a digital signature scheme. (And optionally also a small amount of additional data, which we will discuss next week.)
We consider the corresponding public key also to be their bank account number. These accounts might have money, if (1) someone else has sent money to this account within some transaction in the past and (2) no subsequent transaction has spent the money.
Anyone can create a Bitcoin account. All that is needed is a secret key and public key for a digital signature scheme like ECDSA or Schnorr signatures.
In the snippet of code below, we are creating an actual Bitcoin address right now! (But it has no money, since nobody has signed over their coins to us.)
## WARNING: This code is just for demonstration purposes.
## Do not execute this code to create a Bitcoin key in practice!
## This code does not ensure a safe place to store your secret key.
# !pip install "cryptos @ git+https://github.com/nicolas3355/cryptos"
from cryptos.keys import gen_secret_key, PublicKey
from cryptos.bitcoin import BITCOIN
# generate a secret/public key pair
secret_key = gen_secret_key(BITCOIN.gen.n)
public_key = PublicKey.from_sk(secret_key)
print('generated secret key, in hex format:')
print(hex(secret_key))
print('\ncorresponding public key, as an elliptic curve point:')
print(public_key)
# get the associated bitcoin address
addr = public_key.address(net='main', compressed=True)
print('\ncompressed bitcoin address, in base 58 check format:')
print(addr)
generated secret key, in hex format: 0xfe5ab33d89c05037913f0883816a899096e587b1f34129879121887263d6fe3 corresponding public key, as an elliptic curve point: PublicKey(curve=Curve(p=115792089237316195423570985008687907853269984665640564039457584007908834671663, a=0, b=7), x=29285620428575169888252848216873123226713903519975304285337050457251827757408, y=60257316663837306241142736219388666767475129173325834536877913924619457724853) compressed bitcoin address, in base 58 check format: 1z69QtZWYUMPaaD8EzW6HmTWDxHMsnvvH
Creating an account is easy. Keeping track of this account is a bit harder. If you accidentally delete your secret key, then you will never be able to spend the money in the account -- effectively, your money is gone forever.
We will discuss in a future lecture how we can make it easier for people to keep track of their secret key(s) in a secure way.
Mining a block is hard... and actually this is done on purpose.
Bitcoin needs miners: without them, no money transactions can ever be recorded.
So the Bitcoin system incentivizes people to become miners. If you create or mine a new block, then you get two kinds of rewards:
You get to create new coins out of thin air. Specifically, you get 6.25 Bitcoins, which is worth about $260,000 at current exchange rates. (This is the only way that new Bitcoins get introduced into circulation. In Bitcoin terminology, this is called a coinbase transaction.)
You receive the transaction fees that people set aside for you within their transactions.
For example, this picture shows some of the contents of block number 828285, which was created yesterday on the Bitcoin network.
If all miners act honestly, then the ecosystem works well: people can conduct money transfers over the Internet, and the miners receive a reward for their efforts.
But what if miners are dishonest? What could go wrong?
Just to state upfront:
A bad miner cannot directly create a new transaction to spend your money. Only you can do that, because it requires your secret signing key.
In more detail, thanks to existential unforgeability under a chosen message attack:
Recall that we will consider three categories of security concerns in this course.
Bitcoin doesn't provide any confidentiality guarantees: the whole world knows how much money is in each account. Furthermore, even though people don't write their names on the ledger, it is often possible for an adversary Mallory to link an account to a real-world identity. (More on this later.)
Instead, Bitcoin provides integrity and availability.
Question. Suppose you are a miner and have the power to write blocks on the Bitcoin blockchain. How could you potentially abuse this power to harm integrity and availability?
Here are 3 types of attacks that a malicious miner could perform. (Note: this is not an exhaustive list; there are other possible attacks too.)
[Image source: Bitcoin wiki]
As an example, suppose that Mallory pays Alice and subsequently Alice pays Carol. If a miner deletes the Mallory-to-Alice transaction, then the later transaction becomes invalid as well because Alice no longer has any money to spend.
Even worse, if Mallory is the miner, then Mallory could post a new transaction that pays the money to another account under her own control... perhaps her friend Bob, or perhaps another account held by herself. In this way, Mallory could reclaim her previously-spent money to spend again in the future.
Cryptocurrencies like Bitcoin have been carefully designed to ensure that censorship, inconsistency, and double spending attacks are practically infeasible to perform.
(Note: Bitcoin's protections against these 3 attacks are actually related, but for the purposes of this class, we will treat them separately.)